package digui.tree;

import java.util.Vector;

/**
 * @author cyt
 * @create 2020-05-29 16:42
 */
public class NodeIndex {
    static int layer = 0;

    static Vector<Integer> vector = new Vector<>();

    /**
     * 求 结点到根节点的路径
     *
     * @param args
     */
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);

        node1.left = node2;
        node1.right = node3;
        node2.right = node4;
        node3.left = node5;
        node5.left = node6;
        node4.left = node7;
        node3.right = node8;
        try {
            getNodeLayer(node1, 7);
        } catch (Exception e) {
            e.printStackTrace();
        }

        /**
         *        1
         *   2         3
         *     4     5  8
         *  7       6
         *
         */
    }

    static void getNodeLayer(TreeNode node, int target) {
        layer++;
        if (node.val == target) {
            System.out.println(node.val);
            return;
        }
        if (node.left != null) {
            getNodeLayer(node.left, target);
        }
        if (node.right != null) {
            getNodeLayer(node.right, target);
        }
        layer--;
    }

    /**
     * 得到当前节点到根节点的路径
     *
     * @param node
     * @param target
     */
    static void getNodePath(TreeNode node, int target) {
        layer++;
        vector.add(node.val);
        if (node.val == target) {
            vector.forEach(System.out::println);
            // System.out.println(node.val);
            return;
        }
        if (node.left != null) {
            getNodeLayer(node.left, target);
        }
        if (node.right != null) {
            getNodeLayer(node.right, target);
        }
        layer--;
        Integer integer = vector.lastElement();
        vector.remove(integer);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
